package thread;

import org.junit.Test;

/**
 * @author: feiwang_6
 * @create: 2019/10/31 6:45
 * @description:
 */
public class TestMain {
    
    @Test
    public void testMath(){
        String[] strs = new String[]{"flower","flow","flight"};
        //System.out.println(governPrefix("dog","racecar"));
        System.out.println(commentPrefix(strs));
    }

    public String commentPrefix(String[] strs){
        if(strs.length == 0){
            return "";
        }
        return partArray(strs, 0, strs.length -1);
    }
    
    public String partArray(String[] strs, int l, int r){
        if(r == l){
            return strs[l];
        }else {
            int mid = (l + r) >>> 1;
            String left = partArray(strs, l, mid);
            String right = partArray(strs, mid + 1, r);
            return governPrefix(left, right);
        }
    }
    
    //二分法
    public String governPrefix(String str1, String str2){
        int target = 0;
        int l = 0, r = Math.min(str1.length(), str2.length()) -1;
        while(l <= r){
            int mid = (l+r) >>> 1;
            if(str2.indexOf(str1.substring(0, mid+1)) == 0){
                target = mid+1;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return str1.substring(0, target);
    }
    
    /**
     * 扫描法
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs){
        if(strs.length == 0){
            return "";
        }
        String prefix = strs[0];
        for(int i = 1; i < strs.length; i++){
            while(strs[i].indexOf(prefix) != 0){
                prefix = prefix.substring(0, prefix.length() - 1);
                if(prefix == ""){
                    return "";
                }
            }
        }
        return prefix;
    }
}



